import java.util.Arrays;


// https://leetcode.cn/problems/closest-subsequence-sum/
public class 最接近目标值的子序列和 {

    public static int MAXM = 1 << 20; // 折半查询的最大值
    public static int[] lsum = new int[MAXM]; // 左半边的选和不选的最值
    public static int[] rsum = new int[MAXM]; // 右半边的选和不选的最值
    public static int j; // 这个是 dfs 时的下标
    public static int minAbsDifference(int[] nums, int goal) {
        int n = nums.length;
        // 常数优化
        int max = 0;
        int min = 0;
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (nums[i] >= 0) {
                max += nums[i];
            } else {
                min += nums[i];
            }
        }
        if (max <= goal) return goal - max;
        if (min >= goal) return min - goal;
        // 排序,在 dfs 使用分组 dfs 进行优化, 直接暴力也可以解出来
        Arrays.sort(nums);
        j = 0;
        // 递归左半边并存储
        dfs (0,n / 2,0,lsum,nums);
        int lsize = j;
        j = 0;
        // 递归右半边并存储
        dfs (n / 2,n,0,rsum,nums);
        int rsize = j;
        int a = 0; // 左半边的指针
        int b = rsize - 1; // 右半边的指针
        // 对两个存储的进行排序
        Arrays.sort(lsum,0,lsize);
        Arrays.sort(rsum,0,rsize);
        while (a < lsize && b >= 0) { // 左半边没有到底并且右半边也没有到底
            // 如果右半边往后一个元素减完以后比前一个元素小, 就往后退, 这里有一个单调性存在
            while (b > 0 && Math.abs(goal - lsum[a] - rsum[b]) >= Math.abs(goal - lsum[a] - rsum[b - 1])) {
                b--;
            }
            // 比较并存储返回值
            ans = Math.min(ans,Math.abs(goal - lsum[a] - rsum[b]));
            a++;
        }
        return ans;
    }

    private static void dfs(int a, int b,int v, int[] ans,int[] nums) {
        if (a == b) { // 到底了说明已经完成了选和不选的情况
            ans[j++] = v;
        } else {
            // 分组递归, 前面已经排序过了
            int k = a + 1;
            while (k < b && nums[a] == nums[k]) {
                k++;
            }
            for (int i = 0; i <= k - a; i++) {
                dfs(k,b,v + i * nums[a],ans,nums);
            }
        }
    }
}
